% This is a sample LaTeX input file.  (Version of 9 April 1986) 
% 
% A '%' character causes TeX to ignore all remaining text on the line, 
% and is used for comments like this one.

\documentclass{article}    % Specifies the document style.
\usepackage[pdftex]{graphicx}
\usepackage{cancel}
\usepackage{setspace} % Import setspace package
\usepackage{url}
\usepackage[space]{grffile}
\usepackage{xskak}
\usepackage{fancyvrb}
\usepackage{listings}
\usepackage{tikz}
\usepackage[bottom]{footmisc}
\bibliographystyle{ieeetran}
\usepackage[normalem]{ulem}
\usepackage{algorithmic}
\usepackage[nothing]{algorithm}
\usepackage[strict]{changepage}
\usepackage{soul}
\bibliographystyle{plain}
\linespread{1.6} %Set the iine spacing
								% The preamble begins here.
%\usepackage[retainorgcmds]{IEEEtrantools}
                   
\begin{document}           % End of preamble and beginning of text.
\title{Matrix multiplication}
\maketitle

\pagebreak

\section*{What to do}
Calculating the dot product of two sparse matrices, A $m \times n$, and B $ n \times p $ when they do not fit into RAM poses several challenges.
Approximate matrix multiplication
Storage compression scheme
Parallelization
 
\subsection{Sampling}
Drineas and Kannan \cite{Drineas2006}\cite{Drineasa} give two algorithms for approximating the product of matrices $ A \cdot B $ with provable error bounds. 
The first algorithm (column-row wise) does not require A and B to be stored in RAM. Moreover only 2-3 passes are required for the sampling. 
$ \parallel P - AB\parallel_F $ and $ | P - AB |_2 $ 
\begin{equation}
E(\parallel P - AB \parallel^2 _F) \leq \frac{1}{s} \left( \sum\limits_{k=1}^{n} |A|_{(k)}|B|^{(k)} \right)^2 \leq \\
\frac{1}{s} \parallel A\parallel^2_F \parallel B\parallel^2_F
\end{equation}




\subsection*{Compression}
Compressing sampled matrix\\
\cite{Lin}\cite{Lin2003}

\subsection{Parallelization}
Matrix-multiplication\\
\cite{Bader2006}


\subsection{Implementation}
MapReduce not directly applicable to iterative matrix-multiplication.  \cite{Qiu2010}\cite{Ekanayake2010a} proposes an extension to MapReduce supporting iterative computations effectively


\bibliography{Thesis}
%\nocite{*}
\end{document}